/*
* @Author: HuanXX shy2757539057@163.com
* @Date: 2024-10-12 10:59:37
 * @LastEditors: HuanXX
 * @LastEditTime: 2024-10-19 12:22:03
* @Description: file contentstring
*/
class Main {
    public static void main(String[] args) {
        int[] weight = new int[] {0, 2, 2, 6, 5, 4 };
        int[] value = new int[] {0, 6, 3, 5, 4, 6 };
        int n = weight.length;
        int c = 10;
        int[][] maxvalue = new int[n][c + 1]; //存放m(i, j)的值
        bag(weight, value, n, c, maxvalue);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                System.err.printf("%2d ", maxvalue[i][j]);
            }
            System.err.println();
        }
        traceBack(maxvalue, c, n, weight);
    }

    @SuppressWarnings("ManualArrayToCollectionCopy")
    public static void bag(int[] weight, int[] value, int n, int c, int[][] m) {
        n--;
        // 初始化已知内容
        int Jmax = Math.min(weight[n], c + 1);
        for (int i = 0; i < Jmax; i++) {
            m[n][i] = 0;
        }
        for (int i = weight[n]; i <= c; i++) {
            m[n][i] = value[n];
        }
        //此时所有的m(n, ?)已经定义好了，从n-1开始逐渐求值即可
        for (int i = n - 1; i > 1; i--) {
            Jmax = Math.min(weight[i], c + 1);
            for (int j = 0; j < Jmax; j++) { //放不进去
                m[i][j] = m[i + 1][j];
            }
            for (int j = weight[i]; j <= c; j++) { //放的进去
                m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - weight[i]] + value[i]);
            }
        }
        if (weight[1] <= c) {
            m[1][c] = Math.max(m[2][c], m[2][c - weight[1]] + value[1]);
        } else {
            m[1][c] = m[2][c];
        }
    }

    public static void traceBack(int[][] m, int c, int n, int[] weight) {
        int[] ans = new int[n];
        n--;
        for (int i = 1; i < n; i++) {
            if (m[i][c] == m[i + 1][c]) {
                ans[i] = 0;
            } else {
                ans[i] = 1;
                c -= weight[i];
            }
        }
        if (m[n][c] == 0) {
            ans[n] = 0;
        } else {
            ans[n] = 1;
        }
        for (int i = 1; i < ans.length; i++) {
            System.out.printf("%d ", ans[i]);
        }
        System.out.printf("\n");
    }
}